//package com.starleague.hex.flat;
//
//import com.google.appengine.labs.repackaged.com.google.common.collect.ImmutableList;
//import com.starleague.hex.HexGridUtil;
//import com.starleague.hex.HexPosition;
//
//
//public class FlatHexGridUtil extends HexGridUtil
//{
//	/**
//	 * [x+1][y] is SOUTHEAST of [x][y]
//	 * 
//	 * @param gridX
//	 */
//	private static boolean isUpperY(final int gridX)
//	{
//		return (gridX % 2) != 0;
//	}
//
//	private static transient int LEFT = 1;
//	private static transient int STRAIGHT = 0;
//	private static transient int RIGHT = -1;
//
//	// TODO: Maybe different for Pointy?
//	private static final int turns(
//			final double x0,
//			final double y0,
//			final double x1,
//			final double y1,
//			final double x2,
//			final double y2)
//	{
//		double cross = (x1 - x0) * (y2 - y0) - (x2 - x0) * (y1 - y0);
//		// DEBUG("CROSS: [" + x0 + ", " + y0 + "] to [" + x1 + ", " + y1 +
//		// "] edge [" + x2 + ", " + y2 + "] = " + cross);
//		if (cross < -0.001)
//			return RIGHT;
//		if (cross > 0.001)
//			return LEFT;
//		return STRAIGHT;
//
//		// return((cross > 0) ? LEFT : ((cross==0) ? STRAIGHT : RIGHT));
//	}
//
//	/**
//	 * ASSERT: srcHexPosition != destHexPosition
//	 */
//	@Override
//	protected void calculateLineOfSightPath(
//			final HexPosition srcHexPosition,
//			final HexPosition destHexPosition,
//			final ImmutableList.Builder<HexPosition> listBuilder)
//	{
//		final double src_center_x = (srcHexPosition.getGridX() * 3 + 2) * LOS_HEX_DIV_WIDTH;
//		final double src_center_y = (srcHexPosition.getGridY() * 2 + 1 + ((srcHexPosition.getGridX() + 1) % 2))
//				* LOS_HEX_DIV_HEIGHT;
//
//		final double dest_center_x = (destHexPosition.getGridX() * 3 + 2) * LOS_HEX_DIV_WIDTH;
//		final double dest_center_y = (destHexPosition.getGridY() * 2 + 1 + ((destHexPosition.getGridX() + 1) % 2))
//				* LOS_HEX_DIV_HEIGHT;
//
//		final int min_x = (srcHexPosition.getGridX() < destHexPosition.getGridX())
//				? srcHexPosition.getGridX()
//				: destHexPosition.getGridX();
//		int min_y = (srcHexPosition.getGridY() < destHexPosition.getGridY())
//				? srcHexPosition.getGridY()
//				: destHexPosition.getGridY();
//
//		final int max_x = (srcHexPosition.getGridX() > destHexPosition.getGridX())
//				? srcHexPosition.getGridX()
//				: destHexPosition.getGridX();
//		int max_y = (srcHexPosition.getGridY() > destHexPosition.getGridY())
//				? srcHexPosition.getGridY()
//				: destHexPosition.getGridY();
//
//		if (srcHexPosition.getGridY() == destHexPosition.getGridY())
//		{
//			// Since grid hexes are staggered, we need to include [+1/-1] Y in
//			// some cases
//			--min_y;
//			++max_y;
//		}
//
//		// TODO: start from min_x, instead of 0, and calculate [i % 2] correctly!
//		for (int j = min_y; j <= max_y; ++j)
//			for (int i = min_x; i <= max_x; ++i)
//			{
//				final double x_center = (i * 3 + 2) * LOS_HEX_DIV_WIDTH;
//				final double y_center = (j * 2 + 1 + ((i + 1) % 2)) * LOS_HEX_DIV_HEIGHT;
//
//				// clockwise from [11 o'clock] to [1 o'clock] ...
//				final double xarr[] = { x_center - LOS_HEX_DIV_WIDTH, x_center + LOS_HEX_DIV_WIDTH,
//						x_center + LOS_HEX_DIV_WIDTH * 2, x_center + LOS_HEX_DIV_WIDTH,
//						x_center - LOS_HEX_DIV_WIDTH, x_center - LOS_HEX_DIV_WIDTH * 2 };
//
//				final double yarr[] = { y_center - LOS_HEX_DIV_HEIGHT, y_center - LOS_HEX_DIV_HEIGHT,
//						y_center, y_center + LOS_HEX_DIV_HEIGHT, y_center + LOS_HEX_DIV_HEIGHT, y_center };
//
//				// first see if it intersects the infinite line
//				final int side1 = turns(src_center_x,
//										src_center_y,
//										dest_center_x,
//										dest_center_y,
//										xarr[0],
//										yarr[0]);
//				if (side1 == STRAIGHT)
//				{
//					listBuilder.add(new HexPosition(i, j));
//					// DEBUG("STRAIGHT-1");
//					continue;
//				}
//				for (int corner_indx = 1; corner_indx < 6; ++corner_indx)
//				{
//					int side2 = turns(	src_center_x,
//										src_center_y,
//										dest_center_x,
//										dest_center_y,
//										xarr[corner_indx],
//										yarr[corner_indx]);
//					if (side2 == STRAIGHT || side2 != side1)
//					{
//						// if (side2==STRAIGHT)
//						// DEBUG("STRAIGHT-2");
//						listBuilder.add(new HexPosition(i, j));
//						break;
//					}
//				}
//			}
//	}
//
//}
//
//// public <HEX extends IHex> List<HEX> calculateLineOfSightPath( HEX srcHex, HEX destHex, IHexGrid<HEX>
//// hexGrid) throws HexException
//// {
//// if (srcHex == null)
//// throw new HexException("HexGrid.CalculateLOS(): srcHex is null");
////
//// if (destHex == null)
//// throw new HexException("HexGrid.CalculateLOS(): destHex is null");
////
//// if (srcHex.getP)
//// if (hexGrid.getHexAt(srcHex.getGridX(), srcHex.getGridY()) != srcHex)
//// throw new HexException("HexGrid.CalculateLOS(): srcHex is not on HexGrid: " + srcHex);
////
//// if (this.hexArray2D[destHex.getGridX()][destHex.getGridY()] != destHex)
//// throw new HexException("HexGrid.CalculateLOS(): srcHex is not on HexGrid: " + destHex);
////
//// //
//// //
//// //
////
//// final List<HEX> retList = Lists.newArrayList();
////
//// // TODO: possibly overkill for checking arguments...
//// if (srcHex == destHex)
//// {
//// retList.add(srcHex);
//// return retList;
//// }
////
//// final double src_center_x = (srcHex.getGridX() * 3 + 2) * LOS_HEX_DIV_WIDTH;
//// final double src_center_y = (srcHex.getGridY() * 2 + 1 + ((srcHex.getGridX() + 1) % 2))
//// * LOS_HEX_DIV_HEIGHT;
////
//// final double dest_center_x = (destHex.getGridX() * 3 + 2) * LOS_HEX_DIV_WIDTH;
//// final double dest_center_y = (destHex.getGridY() * 2 + 1 + ((destHex.getGridX() + 1) % 2))
//// * LOS_HEX_DIV_HEIGHT;
////
//// final int min_x = (srcHex.getGridX() < destHex.getGridX()) ? srcHex.getGridX() : destHex.getGridX();
//// int min_y = (srcHex.getGridY() < destHex.getGridY()) ? srcHex.getGridY() : destHex.getGridY();
////
//// final int max_x = (srcHex.getGridX() > destHex.getGridX()) ? srcHex.getGridX() : destHex.getGridX();
//// int max_y = (srcHex.getGridY() > destHex.getGridY()) ? srcHex.getGridY() : destHex.getGridY();
////
//// if (srcHex.getGridY() == destHex.getGridY())
//// {
//// // Since grid hexes are staggered, we need to include [+1/-1] Y in
//// // some cases
//// --min_y;
//// ++max_y;
//// }
////
//// // TODO: start from min_x, instead of 0, and calculate [i % 2] correctly!
//// for (int j = min_y; j <= max_y; ++j)
//// for (int i = min_x; i <= max_x; ++i)
//// {
//// final double x_center = (i * 3 + 2) * LOS_HEX_DIV_WIDTH;
//// final double y_center = (j * 2 + 1 + ((i + 1) % 2)) * LOS_HEX_DIV_HEIGHT;
////
//// // clockwise from [11 o'clock] to [1 o'clock] ...
//// final double xarr[] = { x_center - LOS_HEX_DIV_WIDTH, x_center + LOS_HEX_DIV_WIDTH,
//// x_center + LOS_HEX_DIV_WIDTH * 2, x_center + LOS_HEX_DIV_WIDTH,
//// x_center - LOS_HEX_DIV_WIDTH, x_center - LOS_HEX_DIV_WIDTH * 2 };
////
//// final double yarr[] = { y_center - LOS_HEX_DIV_HEIGHT, y_center - LOS_HEX_DIV_HEIGHT,
//// y_center, y_center + LOS_HEX_DIV_HEIGHT, y_center + LOS_HEX_DIV_HEIGHT, y_center };
////
//// // first see if it intersects the infinite line
//// final int side1 = turns(src_center_x, src_center_y, dest_center_x, dest_center_y, xarr[0],
//// yarr[0]);
//// if (side1 == STRAIGHT)
//// {
//// retList.add(this.hexArray2D[i][j]);
//// // DEBUG("STRAIGHT-1");
//// continue;
//// }
//// for (int corner_indx = 1; corner_indx < 6; ++corner_indx)
//// {
//// int side2 = turns(src_center_x, src_center_y, dest_center_x, dest_center_y,
//// xarr[corner_indx], yarr[corner_indx]);
//// if (side2 == STRAIGHT || side2 != side1)
//// {
//// // if (side2==STRAIGHT)
//// // DEBUG("STRAIGHT-2");
//// retList.add(this.hexArray2D[i][j]);
//// break;
//// }
//// }
//// }
////
//// return retList;
//// }
////
//// public List<HEX> calculateShortestPath(final HEX srcHex, final HEX destHex) throws HexException
//// {
//// if (srcHex == null)
//// throw new HexException("HexGrid.CalculateLOS(): srcHex is null");
////
//// if (destHex == null)
//// throw new HexException("HexGrid.CalculateLOS(): destHex is null");
////
//// if (this.hexArray2D[srcHex.getGridX()][srcHex.getGridY()] != srcHex)
//// throw new HexException("HexGrid.CalculateLOS(): srcHex is not on HexGrid: " + srcHex);
////
//// if (this.hexArray2D[destHex.getGridX()][destHex.getGridY()] != destHex)
//// throw new HexException("HexGrid.CalculateLOS(): srcHex is not on HexGrid: " + destHex);
////
//// //
//// //
//// //
////
//// final List<HEX> retList = Lists.newArrayList();
////
//// // TODO: possibly overkill for checking arguments...
//// if (srcHex == destHex)
//// {
//// retList.add(srcHex);
//// return retList;
//// }
////
//// final double src_center_x = (srcHex.getGridX() * 3 + 2) * LOS_HEX_DIV_WIDTH;
//// final double src_center_y = (srcHex.getGridY() * 2 + 1 + ((srcHex.getGridX() + 1) % 2))
//// * LOS_HEX_DIV_HEIGHT;
////
//// final double dest_center_x = (destHex.getGridX() * 3 + 2) * LOS_HEX_DIV_WIDTH;
//// final double dest_center_y = (destHex.getGridY() * 2 + 1 + ((destHex.getGridX() + 1) % 2))
//// * LOS_HEX_DIV_HEIGHT;
////
//// final int min_x = (srcHex.getGridX() < destHex.getGridX()) ? srcHex.getGridX() : destHex.getGridX();
//// int min_y = (srcHex.getGridY() < destHex.getGridY()) ? srcHex.getGridY() : destHex.getGridY();
////
//// final int max_x = (srcHex.getGridX() > destHex.getGridX()) ? srcHex.getGridX() : destHex.getGridX();
//// int max_y = (srcHex.getGridY() > destHex.getGridY()) ? srcHex.getGridY() : destHex.getGridY();
////
//// if (srcHex.getGridY() == destHex.getGridY())
//// {
//// // Since grid hexes are staggered, we need to include [+1/-1] Y in
//// // some cases
//// --min_y;
//// ++max_y;
//// }
////
//// // FIXME XXX: I think this is the wrong calculation!!! This looks like LOS calculation!
////
//// // TODO: start from min_x, instead of 0, and calculate [i % 2] correctly!
//// for (int j = min_y; j <= max_y; ++j)
//// for (int i = min_x; i <= max_x; ++i)
//// {
//// final double x_center = (i * 3 + 2) * LOS_HEX_DIV_WIDTH;
//// final double y_center = (j * 2 + 1 + ((i + 1) % 2)) * LOS_HEX_DIV_HEIGHT;
////
//// // clockwise from [11 o'clock] to [1 o'clock] ...
//// final double xarr[] = { x_center - LOS_HEX_DIV_WIDTH, x_center + LOS_HEX_DIV_WIDTH,
//// x_center + LOS_HEX_DIV_WIDTH * 2, x_center + LOS_HEX_DIV_WIDTH,
//// x_center - LOS_HEX_DIV_WIDTH, x_center - LOS_HEX_DIV_WIDTH * 2 };
////
//// final double yarr[] = { y_center - LOS_HEX_DIV_HEIGHT, y_center - LOS_HEX_DIV_HEIGHT,
//// y_center, y_center + LOS_HEX_DIV_HEIGHT, y_center + LOS_HEX_DIV_HEIGHT, y_center };
////
//// // first see if it intersects the infinite line
//// final int side1 = turns(src_center_x, src_center_y, dest_center_x, dest_center_y, xarr[0], yarr[0]);
//// if (side1 == STRAIGHT)
//// {
//// retList.add(this.hexArray2D[i][j]);
//// // DEBUG("STRAIGHT-1");
//// continue;
//// }
//// for (int corner_indx = 1; corner_indx < 6; ++corner_indx)
//// {
//// int side2 = turns(src_center_x, src_center_y, dest_center_x, dest_center_y,
//// xarr[corner_indx], yarr[corner_indx]);
//// if (side2 == STRAIGHT || side2 != side1)
//// {
//// // if (side2==STRAIGHT)
//// // DEBUG("STRAIGHT-2");
//// retList.add(this.hexArray2D[i][j]);
//// break;
//// }
//// }
//// }
////
//// return retList;
//// }
////
//// @Override
//// public String toString()
//// {
//// return this.getClass().getSimpleName() + "{minGridX=" + minGridX + ", minGridY=" + minGridY
//// + ", gridWidth=" + gridWidth + ", gridHeight=" + gridHeight + "}";
//// }
//// }
//
//// /*
//// @SuppressWarnings ("unchecked") // 6.0 or later, sometimes 5.0
//// public Grid(final int min_grid_x,
//// final int min_grid_y,
//// final int grid_width,
//// final int grid_height) throws Hex.Exception
//// {
//// if (grid_width <= 0)
//// throw new Hex.Exception("Hex.Grid(): grid_width [" + grid_width +
//// "] is invalid");
//// if (grid_height <= 0)
//// throw new Hex.Exception("Hex.Grid(): grid_height [" + grid_height +
//// "] is invalid");
////
//// _min_grid_x = min_grid_x;
//// _min_grid_y = min_grid_y;
//// _grid_width = grid_width;
//// _grid_height = grid_height;
////
//// _hex_hexnode_map = new HashMap<HEX, Hex.Grid<HEX>.Node>();
////
//// _hexnode_array_2d = new Hex.Grid.Node[_grid_width][_grid_height];
////
//// //ArrayList<Node>[] myarr = (ArrayList<Node>[])
//// //Array.newInstance(ArrayList.class,n);
////
////
//// //
//// // Now populate: this.hexnode_array_2d
//// //
////
//// for (int i = 0; i < this.grid_width; ++i)
//// for (int j = 0; j < this.grid_height; ++j)
//// // create the Node
//// _hexnode_array_2d[i][j] = new Hex.Grid.Node(i, j);
////
//// //
//// // Now populate the edges:
//// this.hexnode_array_2d[i][j]->_edge_hexnode_array[Direction = ...
//// //
////
//// for (int i = 0; i < this.grid_width; ++i)
//// {
//// //if (i == 4) continue;
//// //if (i == 5) continue;
////
//// boolean above_same_grid_y = ((i + this.min_grid_x) % 2) == 1; // [x+1][y] is
//// SOUTHEAST of [x][y]
////
//// for (int j = 0; j < this.grid_height; ++j)
//// {
//// // create the Node
//// //_hexnode_array_2d[i][j] = new Hex.Grid.Node(i, j);
////
//// // Do *EAST edges
//// if (i + 1 < this.grid_width)
//// if (above_same_grid_y)
//// {
//// _hexnode_array_2d[i][j]._edge_hexnode_array.put(Direction.SOUTHEAST,
//// this.hexnode_array_2d[i + 1][j]);
//// _hexnode_array_2d[i + 1][j]._edge_hexnode_array.put(Direction.NORTHWEST,
//// this.hexnode_array_2d[i][j]);
////
//// if (j > 0)
//// {
//// _hexnode_array_2d[i][j]._edge_hexnode_array.put(Direction.NORTHEAST,
//// this.hexnode_array_2d[i + 1][j - 1]);
//// _hexnode_array_2d[i + 1][j - 1]._edge_hexnode_array.put(Direction.SOUTHWEST,
//// this.hexnode_array_2d[i][j]);
//// }
//// }
//// else // !above_same_grid_y
//// {
//// _hexnode_array_2d[i][j]._edge_hexnode_array.put(Direction.NORTHEAST,
//// this.hexnode_array_2d[i + 1][j]);
//// _hexnode_array_2d[i + 1][j]._edge_hexnode_array.put(Direction.SOUTHWEST,
//// this.hexnode_array_2d[i][j]);
////
//// if (j + 1 < this.grid_height)
//// {
//// _hexnode_array_2d[i][j]._edge_hexnode_array.put(Direction.SOUTHEAST,
//// this.hexnode_array_2d[i + 1][j + 1]);
//// _hexnode_array_2d[i + 1][j + 1]._edge_hexnode_array.put(Direction.NORTHWEST,
//// this.hexnode_array_2d[i][j]);
//// }
//// }
////
//// // Do *WEST edges
//// if (i > 0)
//// if (above_same_grid_y)
//// {
//// _hexnode_array_2d[i][j]._edge_hexnode_array.put(Direction.SOUTHWEST,
//// this.hexnode_array_2d[i - 1][j]);
//// _hexnode_array_2d[i - 1][j]._edge_hexnode_array.put(Direction.NORTHEAST,
//// this.hexnode_array_2d[i][j]);
////
//// if (j > 0)
//// {
//// _hexnode_array_2d[i][j]._edge_hexnode_array.put(Direction.NORTHWEST,
//// this.hexnode_array_2d[i - 1][j - 1]);
//// _hexnode_array_2d[i - 1][j - 1]._edge_hexnode_array.put(Direction.SOUTHEAST,
//// this.hexnode_array_2d[i][j]);
//// }
//// }
//// else // !above_same_grid_y
//// {
//// _hexnode_array_2d[i][j]._edge_hexnode_array.put(Direction.NORTHWEST,
//// this.hexnode_array_2d[i - 1][j]);
//// _hexnode_array_2d[i - 1][j]._edge_hexnode_array.put(Direction.SOUTHEAST,
//// this.hexnode_array_2d[i][j]);
////
//// if (j + 1 < this.grid_height)
//// {
//// _hexnode_array_2d[i][j]._edge_hexnode_array.put(Direction.SOUTHWEST,
//// this.hexnode_array_2d[i - 1][j + 1]);
//// _hexnode_array_2d[i - 1][j + 1]._edge_hexnode_array.put(Direction.NORTHEAST,
//// this.hexnode_array_2d[i][j]);
//// }
//// }
////
//// // Do NORTH edge
//// if (j > 0)
//// {
//// _hexnode_array_2d[i][j]._edge_hexnode_array.put(Direction.NORTH,
//// this.hexnode_array_2d[i][j - 1]);
//// _hexnode_array_2d[i][j - 1]._edge_hexnode_array.put(Direction.SOUTH,
//// this.hexnode_array_2d[i][j]);
//// }
////
//// // Do SOUTH edge
//// if (j + 1 < this.grid_height)
//// {
//// _hexnode_array_2d[i][j]._edge_hexnode_array.put(Direction.SOUTH,
//// this.hexnode_array_2d[i][j + 1]);
//// _hexnode_array_2d[i][j + 1]._edge_hexnode_array.put(Direction.NORTH,
//// this.hexnode_array_2d[i][j]);
//// }
//// }
//// }
//// }
////
//// public boolean AddHex(final int grid_x, final int grid_y, HEX hex)
//// {
//// // We do not support adding NULL Hexes
//// if (hex == null)
//// return false;
////
//// if ((grid_x < this.min_grid_x) || (grid_x >= this.min_grid_x +
//// this.grid_width))
//// return false;
////
//// if ((grid_y < this.min_grid_y) || (grid_y >= this.min_grid_y +
//// this.grid_height))
//// return false;
////
//// _hexnode_array_2d[grid_x - this.min_grid_x][grid_y -
//// this.min_grid_y]._hex = hex;
//// _hex_hexnode_map.put(hex, this.hexnode_array_2d[grid_x -
//// this.min_grid_x][grid_y - this.min_grid_y]);
////
//// return true;
//// }
////
//// public HEX getHex(final int grid_x, final int grid_y)
//// {
//// if ((grid_x < this.min_grid_x) || (grid_x >= (long)(this.min_grid_x +
//// this.grid_width)))
//// return null;
////
//// if ((grid_y < this.min_grid_y) || (grid_y >= (long)(this.min_grid_y +
//// this.grid_height)))
//// return null;
////
//// return this.hexnode_array_2d[grid_x - this.min_grid_x][grid_y -
//// this.min_grid_y]._hex;
//// }
////
//// public HEX getHexInDirection(HEX start_hex, final Hex.Direction
//// direction)
//// {
//// Hex.Grid<HEX>.Node start_node = this.hex_hexnode_map.get(start_hex);
//// if (start_node != null)
//// {
//// Hex.Grid<HEX>.Node end_node =
//// start_node._edge_hexnode_array.get(direction);
//// if (end_node != null)
//// return end_node._hex;
//// }
//// return null;
//// }
////
//// public Hex.Position getHexPosition(HEX hex)
//// {
//// Hex.Grid<HEX>.Node node = this.hex_hexnode_map.get(hex);
//// if (node != null)
//// {
//// return new Hex.Position(node.getGridX(), node.getGridY());
//// }
//// return null;
//// }
////
//// private class Node
//// {
//// final int grid_x;
//// final int grid_y;
////
//// Node(final int grid_x, final int grid_y)
//// {
//// grid_x = grid_x;
//// grid_y = grid_y;
//// _hex = null;
//// _edge_hexnode_array = new HashMap<Hex.Direction,
//// Hex.Grid<HEX>.Node>(Hex.Direction.values().length);
//// // TODO: I SHOULD null out this.edge_hexnode_array[*], but we immediately
//// populate it in the constructor...
//// }
////
//// //private Hex.IHex this.ihex;
//// private HEX this.hex;
//// private final Map<Hex.Direction, Hex.Grid<HEX>.Node> this.edge_hexnode_array;
//// //Hex::HexGrid::HexNode *_edge_hexnode_array[Hex::DIRECTION_SIZE];
//// }
////
//// private final int this.min_grid_x;
//// private final int this.min_grid_y;
//// private final int this.grid_width;
//// private final int this.grid_height;
//// private final Map<HEX, Hex.Grid<HEX>.Node> this.hex_hexnode_map;
//// private final Hex.Grid<HEX>.Node this.hexnode_array_2d[][];
//// }
////
//// */
